Digital computers are widely available which have microprogram controlled central processors. In such computers, the execution of a single "machine-language" instruction from an instruction stream in main storage can entail the execution of a sequence of more elementary instructions, generally termed microinstructions or control words. For example, a machine-language instruction to add two numbers located in main storage and store the sum in the memory location of one of them might involve a sequence of nine microinstructions: (1) load the address of the first addend in a main-store address register; (2) read the contents of the main store location specified in the main-store address register; (3) transfer the first addend from a main-store read output register to a first register in the central processor; (4) load the address of the second addend in the main-store address register; (5) read the contents of the main store location specified in the main-store address register; (6) transfer the second addend from the main-store read output register to a second register in the central processor; (7) add the contents of the first and second registers and store the sum in the first register; (8) transfer the contents of the first register to a main-store write input register; and (9) write the contents of the write input register into the memory location specified by the address register. Microinstructions are generally stored in a memory termed the control store. The control store is typically, but not necessarily, separate from the main storage units of the computer.
In a typical digital computer having a microprogram-controlled central processor, microinstruction routines define the machine-language instructions executed by the processor, as well as specify certain control functions for the computer such as directing input/output data transfers. To provide for machine-language instructions which call for accessing main storage, the microinstruction repertoires of such computers include microinstructions for controlling access to main storage. Descriptions of digital computers having conventional microprogram-controlled central processing units may be found in the following two books and in the references cited therein: Foundations of Microprogramming by Ashok K. Agrawala and Tomlinson G. Rauscher (Academic Press, Inc. 1976) and Microprogramming Principles and Practices by Samir S. Husson (Prentice-Hall, Inc. 1970).
A significant drawback of microprogram-controlled central processing units is the longer time ordinarily required to execute machine-language instructions as compared to execution times in processors which implement machine-language instructions with hardwired logic circuits. Since operation of a microprogram-controlled central processing unit involves execution of sequences of microinstructions, the speed of the processor is determined, in part, by the time required to execute the various microinstructions. Circuits for microprogrammed central processors have been devised which attempt to minimize the execution time of microinstructions, including those which involve accessing main storage, but none of these circuits provides a completely satisfactory balance between complexity, and thus cost, and speed of execution.
A known technique for reducing the time to carry out a sequence of microinstructions involves overlapping the execution of the current microinstruction with the fetching of the next microinstruction from the control store. This overlapping technique has been termed parallel implementation. As pointed out on pages 77-79 of the book by Agrawala and Rauscher, a problem can arise with parallel implementation when microinstructions containing conditional branch microoperations are to be executed. In this case the address of the next microinstruction in control store may not be determined until the end of the execution phase of the current microinstruction, which precludes overlapping the fetching of the next microinstruction with the execution of the current one. In such cases a combined serial-parallel implementation is necessary, in which fetching of the next microinstruction is carried out in parallel with the execution of the current microinstruction unless the current microinstruction involves a conditional branch. It is noted in the cited passage that the performance of combined serial-parallel implementation can be improved by guessing that the tested condition will be true and fetching in parallel the microinstruction at the guessed address. A serial fetch is thus required only when the guess is not correct. However, since such a guess would be essentially arbitrary in general, it is to be expected that the guess would turn out to be incorrect a significant fraction of the time.